1. Field of the Invention
The present invention relates to a scheme for computing Montgomery division and Montgomery inverse to be used in processing that repeatedly utilizes multiple-precision arithmetic operations modulo an odd integer, such as that of public key cryptosystem which is utilized for data encryption and correspondent authentication in data communications on computer networks.
2. Description of the Background Art
Information communications networks and computer systems require exchanges and storing of electronic information, and when such a system becomes large scale so that unspecified many users utilize such a system, there arises problems of eavesdropping or alteration of information by a malicious user. As a measure against such a malicious user, the public key cryptosystem technique is often employed.
Public key cryptosystem is mostly realized in terms of arithmetic operations modulo a multiple-precision odd integer, and their fast implementation can affect a performance of the public key crypstosystem. Among arithmetic operations modulo a multiple-precision odd integer, multiplications and divisions have particularly large influences on processing time. As for multiplications, there is a computational algorithm suitable for a case of repeatedly executing multiplications, called Montgomery method. For details, see Reference (1): P. L. Montgomery, "Modular multiplication without trial division", Mathematics of Computation, Vol. 44, No. 170, pp. 519-521 (1985).
The Montgomery method is a method for computing multiple-precision modular multiplication by a processing amount of about two multiple-precision multiplications. Multiple-precision modular reduction usually has a poorer performance compared with multiple-precision multiplication so that it is possible to realize that much faster implementation. This Montgomery method is a multiplication algorithm for elements in Montgomery space (which define the same integers modulo p), where two numbers to be multiplied are converted into the Montgomery space first, then the Montgomery multiplication is carried out, and finally the result is inversely converted from the Montgomery space to original integers modulo p. Each of the Montgomery conversion and the inverse Montgomery conversion requires a processing amount of about one multiple-precision multiplication, so that modular exponentiation suffers less overhead due to the Montgomery conversion and the inverse Montgomery conversion because it carries out modular multiplications repeatedly and therefore it can be realized by a fast implementation.
Since many public key cryptosystems including RSA (Rivest-Shamir-Adleman) cryptosystem are using modular exponentiation c=m.sup.e mod N as their basic operation, the Montgomery method can be effectively utilized for them (although the Montgomery method may not necessarily lead to efficient implementation in cases where only some multiplications are required because of the overhead due to the Montogomery conversion and the inverse Montgomery conversion).
Now, in recent years, various new crypstosystems have been studied and proposed, and in particular the elliptic curve cryptosystem has been attracting much attentions among public key cryptosystems. This elliptic curve cryptosystem is based on a conjecture that the problem of discrete logarithm over elliptic curves is more difficult to solve computationally than the factorization of composites on which the RSA cryptosystem is based.
Here, basic operations in the elliptic curve cryptosystem will be described briefly.
In finite field Fp (p&gt;3), curves defined by: EQU E(a, b)/Fp: y.sup.2 =x.sup.3 +ax+b mod p
where a and b are integers for which 0.ltoreq.a, b&lt;p and 4a.sup.3 +27b.sup.2 .noteq.0 mod p, are called elliptic curves in finite field Fp. Points on eplliptic curves are defined to be sets (x, y) that satisfy the above equation (where x and y are integers for which 0.ltoreq.x, y&lt;p) plus a point at infinity 0. This point at infinity 0 serves as a unit element for addition.
Points on elliptic curves form a group for addition as follows. Namely, a sum S(x.sub.3, y.sub.3) of points P=(x.sub.1, y.sub.1) and Q=(X.sub.2, y.sub.2) on elliptic curves can be given by the following, where -P=(x.sub.1, -y.sub.1).
(1) When Q is a unit element 0: EQU S=P+Q=Q+P=P PA1 (2) When Q=-P: EQU S=P+Q=Q+P=0 PA1 (3) When P.noteq.Q (other than (1) and (2)): EQU x.sub.3 =(y.sub.2 -y.sub.1).sup.2 /(x.sub.2 -x.sub.1).sup.2 -x.sub.1 -x.sub.2 mod p EQU y.sub.3 =(y.sub.2 -y.sub.1)(x.sub.1 -x.sub.3)/(x.sub.2 -x.sub.1)-y.sub.1 mod p PA1 (4) When P=Q:
if y1.noteq.0: EQU x.sub.3 =(3x.sub.1.sup.2 +a).sup.2 /(2y.sub.1).sup.2 -2x.sub.1 mod p EQU y.sub.3 =(3x.sub.1.sup.2 +a)(x.sub.1 -x.sub.3)/(2y.sub.1)-y.sub.1 mod p PA2 if y.sub.1 =0:
S=0
Also, an e (integer) multiple of a point (x.sub.1, y.sub.1) on elliptic curves is defined as iterations of the above described addition by the following. EQU eP=P+P+ . . . +P (P is added e times)
Note however that when e&lt;0, an (-e) multiple of a point (-P) is to be calculated (where (-e) is a positive), and when e=0, it is set that 0P=0.
In the elliptic curve cryptosystem, the basic operation is a scalar multiple operation (iteration of additions) of a point on elliptic curves. This operation occupies the major part of the processing required in elliptic El Gamal cryptosystem, elliptic El Gamal Signature scheme, and elliptic DH (Diffie-Hellman) scheme, for example.
Thus, in contrast to the RSA cryptosystem which uses modular multiplication as the basic operation, the elliptic curve cryptosystem require four arithmetic operations in order to realize its basic operation.
Now, when the basic operation is iterated processing of multiple-precision arithmetic operations as in the elliptic curve cryptosystem, processing time consuming operations among arithmetic operations are modular multiplication and modular division so that it is necessary to realize a fast impelmentation of these modular multiplication and modular division in order to realize a fast implementation of the entire cryptographic processing. Of these, the modular multiplication can be realized by a fast implementation using the Montgomery multiplication algorithm of the above noted Reference (1), for example.
On the other hand, the modular division can be realized as a combination of (multiplicative) inverse calculation and modular multiplication, and in general an inverse can be calculated by a method called extended Euclidean division algorithm. However, this algorithm is not very fast in general. As a fast inverse calculation scheme, there is a conventionally known scheme using multiple-precision ingeter right-shift (multiplication by 1/2), addition and subtraction. For details, see Reference (2): B. S. Kaliski Jr., "The Montgomery Inverse and Its Application", IEEE Transactions on Computers, Vol. 44, No. 8, pp. 1064-1065 (August 1995).
However, the Montgomery multiplication of the Reference (1) and the fast modular division calculation scheme of the Reference (2) cannot be directly utilized because it would then become necessary to carry out the Montgomery conversion and the inverse Montgomery conversion between the Montgomery space and original integers modulo p every time a multiplication or a division is to be carried out and this requirement in turn would cause a very large overhead.
Moreover, there has been no known algorithm that can efficiently calculate modular division in the Montgomery space.
Thus it has conventionally been difficult to realize a fast implementation of modular division, and consequently it has conventionally difficult to realize a fast implementation of cryptographic processing in which the basic operation is iterated processing of arithmetic operations (modular arithmetic) as in the case of elliptic curve cryptosystems.
As described, there has been no known scheme for efficiently realizing iterated processing of operations including modular multiplication and modular division, and it has conventionally been difficult to realize an efficient implementation of the entire processing for elliptic curve cryptosystem and the like.